package com.sunny.排序.插入排序;

import com.sunny.util.ArrayUtil;

public class InsertSort {
    public static int[] insertSort(int size) {
         // 开始时间
        long start = System.currentTimeMillis();
        // 初始化数组
        int[] array = ArrayUtil.instanceArray(size);
        // 排序
        int length = size -1; // 单独把数组长度拿出来，提高效率
        for(int i = 1; i < size; ++i) {// 因为第一次不用，所以从1开始
            int insertNum = array[i];
            int j = i - 1; // 序列元素个数
            while(j >= 0 && array[j] > insertNum) { // 从后向前循环，将大于insertNum的数据向后移动
                array[j+1] = array[j]; // 元素向后移动
                j--;
            }
            array[j + 1] = insertNum; // 找到位置插入当前元素
        }

        // 结束时间
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));
        return array;
    }
}
